Kubu ini dirancang oleh Sultan Mahmud Badaruddin I (1724-1758) dan dibina oleh anaknya, Sultan Mahmud Bahauddin (1776-1801).[1] Pembinaannya mengambil masa tujuh belas tahun untuk disiapkan, dan ia akhirnya dirasmikan pada tahun 1790.[1]

Sejak pembinaannya, Benteng Kuto Besak telah berkhidmat sebagai simbol keyakinan penentangan tempatan kepada kuasa-kuasa Eropah, iaitu Britain dan Belanda.[1] Kubu ini di bawah kepimpinan Sultan Mahmud Badaruddin II mengalami tiga kali serangan Belanda, yang cuba untuk menakluk Kesultanan Palembang. Serangan pertama pada Julai 1819 di bawah kepimpinan Pesuruhjaya H.W. Muntinghe mahupun serangan kedua pada Oktober 1819 di bawah kepimpinan Laksamana Muda C.J. Wolterbeek tidaklah berjaya, dan tentera Belanda dapat ditangkis.[4] Barulah pada serangan ketiga pada Jun 1821 di bawah kepimpinan Jeneral H.M. de Kock, Belanda dapat berjaya menembusi pertahanan kubu ini.[4] Sultan Mahmud Badaruddin II kemudiannya ditangkap, dan dibuang ke Ternate, Maluku Utara.[5]

Selepas pengambilalihan kuasa oleh Belanda pada 1823, mereka menempatkan tenteranya di kubu ini.[1] Keadaannya sekali lagi bertukar oleh penempatan tentera Indonesia, iaitu selepas Kemerdekaan Indonesia[2]